class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0){
            return 0;
        }
        /*
        int min=prices[0];
        int max_after_min=prices[0];
        for(int i=0;i<prices.size();i++){
            if(prices[i]<min){
                min=prices[i];
                max_after_min=prices[i];
            }
            if(prices[i]>max_after_min){
                max_after_min=prices[i];
            }
        }
        return max_after_min-min;
        */
        /*
        int left=0;
        int right=0;
        int max=0;
        for(int i=0;i<prices.size();i++){
            if(prices[i]<prices[left]){
                left=i;
                right=i;
            }
            if(prices[i]>prices[right]){
                right=i;
            }
            if(left<right){
                if((prices[right]-prices[left])>max){
                    max=prices[right]-prices[left];
                }
            }
        }
        return max;
        */
        int min=prices[0];
        int profile=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min){
                min=prices[i];
            } else{
                profile=profile>prices[i]-min?profile:prices[i]-min;
            }
        }
        return profile;
    }
};

//复习时再次做
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        /*
        vector<vector<int>> dp(prices.size()+1,vector<int>(2,0));
        dp[0][1]=INT_MIN;
        for(int i=0;i<prices.size();i++){
            dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]);
            dp[i+1][1]=max(dp[i][1],-prices[i]);
            //cout<<"no "<<dp[i+1][0]<<" "<<"yes "<<dp[i+1][1]<<endl;
        }
        return dp[prices.size()][0];
        */

        
        int dp_i_0=0;//dp[i][0]
        int dp_i_1=INT_MIN;//dp[i][1]
        for(int i=0;i<prices.size();i++){
            //cout<<"no "<<dp[i+1][0]<<" "<<"yes "<<dp[i+1][1]<<endl;
            dp_i_0=max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1=max(dp_i_1,-prices[i]);
        }
        return dp_i_0;
    }
};

// dp[int][freq][bool] 第k天 ,买卖次数,状态（0，手上没有，1，手上有）
// dp[k][1][0]=max(dp[k-1][1][0],dp[k-1][1][1]+prices[k])
// dp[k][1][1]=max(dp[k-1][1][1],dp[k-1][0][0]-prices[k])


//2020.8.12 维护一个最低值
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low=INT_MAX;
        int max_profit=0;
        for(int i=0;i<prices.size();i++){
            if(prices[i]>low){
                max_profit=max(max_profit,prices[i]-low);
            }
            if(prices[i]<low){
                low=prices[i];
            }
        }
        return max_profit;
    }
};